package cn.hdr.train.lc;


import cn.hdr.train.bean.TreeNode;

import java.util.*;

public class LCTestB {

    public void sort(int[] nums){
        sort(nums,0,nums.length - 1);
    }
    public void sort(int[] nums,int start,int end){
        if(start >= end)
            return;

        int mid = nums[(start + end) >> 1];
        int i = start;
        int j = end;
        while (i < j){
            while (i < j && nums[i] <= mid) i++;
            while (i < j && nums[j] >= mid) j--;
            if(i < j){
                swap(nums,i,j);
            }
        }
        sort(nums,start,j - 1);
        sort(nums,j + 1,end);
    }

    private void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }


    public void heapSort(int[] arr){
        for(int i = arr.length - 1; i > 0; i--){
            max_heapify(arr, i);
            System.out.println(Arrays.toString(arr));
            swap(arr,0,i);
            System.out.println(Arrays.toString(arr));
        }
    }

    private void max_heapify(int[] arr, int end){
        for(int p = (end - 1) / 2; p >= 0; p--){
            int left = p * 2 + 1;       //左子节点位置
            int right = (left + 1) > end ? left : (left + 1);    //右子节点位置，如果没有右节点，默认为左节点位置

            int maxChildId = arr[left] >= arr[right] ? left : right;
            if(arr[maxChildId] > arr[p]){   //交换父节点与左右子节点中的最大值
                swap(arr,p,maxChildId);
            }
        }
    }

    public int[] mergingSort(int[] nums){
        if(nums == null || nums.length <= 1)
            return nums;

        int mid = nums.length >> 1;

        int[] leftArr = Arrays.copyOfRange(nums,0,mid);
        int[] rightArr = Arrays.copyOfRange(nums,mid,nums.length);

        return mergeTwoArray(mergingSort(leftArr),mergingSort(rightArr));
    }
    public int[] mergeTwoArray(int[] aArr,int[] bArr){
        int l = 0,r = 0,i = 0;
        int[] newArr = new int[aArr.length + bArr.length];
        while (l < aArr.length && r < bArr.length){
            if(aArr[l] < bArr[r]){
                newArr[i++] = aArr[l++];
            }else {
                newArr[i++] = bArr[r++];
            }
        }
        while (l < aArr.length){
            newArr[i++] = aArr[l++];
        }
        while (r < bArr.length){
            newArr[i++] = bArr[r++];
        }
        return newArr;
    }

    public void shell_sort(int[] arr) {
        int gap = 1, i, j, len = arr.length;
        int temp;
        while (gap < len / 3)
            gap = gap * 3 + 1;      // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...


        for (; gap > 0; gap /= 3) {
            for (i = gap; i < len; i++) {
                temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                    arr[j + gap] = arr[j];
                arr[j + gap] = temp;
            }
        }
    }

    public static void insertionSort(int[] arr){
        for( int i = 1; i < arr.length; i++ ) {
            System.out.println(Arrays.toString(arr));
            int temp = arr[i];    // 取出下一个元素，在已经排序的元素序列中从后向前扫描
            for( int j = i; j >= 0; j-- ) {
                if( j > 0 && arr[j-1] > temp ) {
                    arr[j] = arr[j-1];    // 如果该元素（已排序）大于取出的元素temp，将该元素移到下一位置
                } else {
                    // 将新元素插入到该位置后
                    arr[j] = temp;
                    break;
                }
            }
        }
    }

    int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] f = new int[max];
        Arrays.fill(f, 100);
        f[0] = 0;
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                f[j] = Math.min(f[j], f[j - coin] + 1);
            }
        }
        System.out.println(Arrays.toString(f));
        return f[amount] <= amount? f[amount] : -1;
    }



    int coinChange1(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        Arrays.fill(f, -2);
        return coinChange1Support(coins,amount,f);
    }

    int coinChange1Support(int[] coins, int amount,int[] arr){
        if(amount <= 0)
            return 0;
        int num = Integer.MAX_VALUE;
        for (int coin : coins) {
            int v = amount - coin;
            if (v >= 0) {
                if (arr[v] == -2) {
                    arr[v] = coinChange1Support(coins, v, arr);
                }
                if (arr[v] != -1) {
                    num = Math.min(arr[v] + 1, num);
                }
            }
        }
        arr[amount] = num > amount ? -1 : num;
        return arr[amount];
    }

    int coinChange0(int[] coins, int amount) {
        if(amount <= 0)
            return 0;
        int num = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (amount >= coin) {
                int value = coinChange(coins, amount - coin);
                if (value != -1) {
                    num = Math.min(value + 1, num);
                }
            }
        }
        return num > amount ? -1 : num;
    }


    /**
     * 输入: [1,null,2,3]
     *    1
     *     \
     *      2
     *     /
     *    3
     * 给定一个二叉树，返回它的中序 遍历。
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ldr = new ArrayList<>();
        TreeNode cur = root;
        TreeNode pre;
        while(cur!=null){
            if(cur.left==null){//左子树为空，输出当前节点，将其右孩子作为当前节点
                ldr.add(cur.val);
                cur = cur.right;
            }
            else{
                pre = cur.left;//左子树
                while(pre.right!=null&&pre.right!=cur){//找到前驱节点，即左子树中的最右节点
                    pre = pre.right;
                }
                //如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
                if(pre.right==null){
                    pre.right = cur;
                    cur = cur.left;
                }
                //如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
                if(pre.right==cur){
                    pre.right = null;
                    ldr.add(cur.val);
                    cur = cur.right;
                }
            }
        }
        return ldr;
    }


    public List<Integer> inorderTraversal0(TreeNode root) {
        if(root == null)
            return new ArrayList<>(0);

        TreeNode p = root;
        List<Integer> list = new ArrayList<>(inorderTraversal0(p.left));
        list.add(p.val);
        list.addAll(inorderTraversal0(p.right));
        return list;
    }


    /**
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
     *
     * 说明：
     *
     * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
     *
     * 示例 1:
     *
     * 输入: [2,2,3,2]
     * 输出: 3
     * 示例 2:
     *
     * 输入: [0,1,0,1,0,1,99]
     * 输出: 99
     *
     */
    public int singleNumber(int[] nums) {
        int v = nums[0];
        for (int i = 1; i < nums.length; i++) {
            v ^= nums[i];
        }
        return v;
    }
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public void reorderList(ListNode head) {
        if(head == null){
            return ;
        }
        //1. 使用快慢指针,找出链表的中心节点。
        // 1->2->3->4->5,中心节点为3
        ListNode middle = middleNode(head);

        //2. 将原始链表按照中心链表分割为两个链表，并将右链表反转
        //2.1 原始链表：1->2->3->4->5 左链表：1->2->3 右链表：4->5
        ListNode left = head;
        ListNode right = middle.next;
        middle.next = null;

        //2.2 反转右链表
        //原始右链表：4->5 反转后：5->4
        right = reverse(right);

        //3. 合并两个链表，将右链表插入到左链表
        //左链表：1->2->3 右链表：4->5 合并后：1->5->2->4->3
        merge(left,right);
    }

    //1. 使用快慢指针,找出链表的中心节点
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //2. 通过递归反转链表
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //反转mid
        ListNode v1 = head;
        ListNode v2 = head.next;
        v1.next = null;
        while (true){
            ListNode temp = v2.next;
            v2.next = v1;
            if(temp == null){
                break;
            }
            v1 = v2;
            v2 = temp;
        }
        return v2;
    }

    //3. 合并两个链表，将右链表插入到左链表
    public void merge(ListNode left, ListNode right){
        ListNode leftTemp;
        ListNode rightTemp;
        while (left.next != null && right!= null) {
            //1. 保存next节点
            leftTemp = left.next;
            rightTemp = right.next;

            //2. 将右链表的第一个节点插入到左链表中
            // 左链表：1->2->3 右链表：5->4
            // 合并后的左链表：1->5->2->3
            left.next = right;
            right.next = leftTemp;

            //3. 移动left和right指针
            //左链表变为：2->3 右链表变为：4
            left = leftTemp;
            right = rightTemp;
        }
    }


    public int test(int[] nums){
        if(nums == null || nums.length == 0) return -1;
        int leftNum = 0;
        int rightNum = 0;
        for (int num:nums) {
            rightNum += num;
        }
        for (int i = 0; i < nums.length; i++) {
            rightNum -= nums[i];
            if(i >= 1)
                leftNum += nums[i - 1];
            if(leftNum == rightNum)
                return i;
        }
        return -1;
    }


    /**
     * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 示例:
     *
     * 输入:
     *
     *    1
     *  /   \
     * 2     3
     *  \
     *   5
     *
     * 输出: ["1->2->5", "1->3"]
     *
     * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
     *
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        support(root,new StringBuilder(),list);

        return list;
    }

    public void support(TreeNode node,StringBuilder pre,List<String> list){
        if(node == null)
            return;
        StringBuilder n = new StringBuilder(pre);
        if(pre.length() != 0){
            n.append("->");
        }
        n.append(node.val);
        if(node.left == null && node.right == null){
            list.add(n.toString());
            return;
        }
        support(node.left,n,list);
        support(node.right,n,list);
    }


    /**
     * 给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
     *
     * 示例:
     *
     * 输入: 38
     * 输出: 2
     * 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
     *
     */
    public int addDigits(int num) {
        if(num < 10)
            return num;

        char[] vArr = (num + "").toCharArray();
        int all = 0;
        for (char c:vArr) {
            all += c - '0';
        }
        return addDigits(all);
    }

    public boolean isPowerOfThree(int n) {
        if(n <= 0)
            return false;

        long tar = 1;
        while (tar < n){
            tar *= 3;
        }
        return tar == n;
    }

    public int sumOfLeftLeaves(TreeNode root) {

        return sumOfLeftLeavesSup(root,false);
    }

    private int sumOfLeftLeavesSup(TreeNode root,boolean left){
        if(root == null)
            return 0;
        if(left && root.left == null && root.right == null){
            return root.val;
        }

        return sumOfLeftLeavesSup(root.left,true) + sumOfLeftLeavesSup(root.right,false);
    }

    /**
     * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
     *
     * 示例 1:
     *
     * 输入: 1->1->2
     * 输出: 1->2
     * 示例 2:
     *
     * 输入: 1->1->2->3->3
     * 输出: 1->2->3
     *
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode start = head;
        while (start != null && start.next != null){
            ListNode ln= start.next;
            if(start.val == start.next.val){
                start.next = start.next.next;
                ln.next = null;
            }else {
                start = start.next;
            }
        }
        return head;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        if(p == null || q == null)
            return false;

        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

    }


    /**
     * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 示例: 
     * 给定如下二叉树，以及目标和 sum = 22，
     *
     *               5
     *              / \
     *             4   8
     *            /   / \
     *           11  13  4
     *          /  \      \
     *         7    2      1
     * 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
     *
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null)
            return false;

        if(root.left == null && root.right ==null)
            return root.val == sum;

        return hasPathSum(root.left,sum - root.val) || hasPathSum(root.right,sum - root.val);
    }


    /**
     * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
     *
     * 说明：每次只能向下或者向右移动一步。
     *
     * 示例:
     *
     * 输入:
     * [
     *   [1,3,1],
     *   [1,5,1],
     *   [4,2,1]
     * ]
     * 输出: 7
     * 解释: 因为路径 1→3→1→1→1 的总和最小。
     *
     */
    public int minPathSum(int[][] grid) {
        cache = new int[grid.length][grid[0].length];
        return minPathSumSupport(grid,0,0);
    }

    int[][] cache = null;

    public int minPathSumSupport(int[][] grid, int left, int top) {
        if(left == grid[0].length - 1  && top == grid.length - 1)
            return grid[top][left];

        if(cache[top][left] != 0)
            return cache[top][left];

        int value1,value2;
        if(left + 1 >= grid[0].length){
            value1 = Integer.MAX_VALUE;
        }else {
            value1 = minPathSumSupport(grid,left+1,top);
        }

        if(top + 1 >= grid.length){
            value2 = Integer.MAX_VALUE;
        }else {
            value2 = minPathSumSupport(grid,left,top+1);
        }

        cache[top][left] = grid[top][left] + Math.min(value1, value2);

        return cache[top][left];
    }


    /**
     * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
     *
     * 示例 1:
     * 输入: 1->2->3->3->4->4->5
     * 输出: 1->2->5
     *
     * 示例 2:
     * 输入: 1->1->1->2->3
     * 输出: 2->3
     *
     */
    public ListNode deleteDuplicates1(ListNode head) {
        if(head == null)
            return null;

        ListNode pre = new ListNode(0);
        pre.next = head;

        ListNode headPre = pre;
        while (head.next != null){
            boolean flag = false;
            while (head.next != null && head.val == head.next.val){
                head.next = head.next.next;
                flag = true;
            }
            if(flag){
                headPre.next = headPre.next.next;
            }else {
                headPre = head;
            }
            head = headPre.next;
        }

        return pre.next;
    }

    /**
     *      4   1
     *              8   4   5
     *  5   0   1
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int al = getLength(headA);
        int bl = getLength(headB);
        while (al != bl){
            if(al > bl){
                headA = headA.next;
                al--;
            }else {
                bl--;
                headB = headB.next;
            }
        }
        while (headA != headB){
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }

    private int getLength(ListNode node){
        int i = 0;
        for (;node != null;i++){
            node = node.next;
        }
        return i;
    }

    /**
     *      4   1
     *              8
     *  5   0   1
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    public static void main(String[] args) {

    }

}